package com.zyj.test.month1.day16;


/**
 * @author Yijia Zhang
 * @create 2024-06-05 21:01
 */
public class code0031 {
    public void nextPermutation(int[] nums) {
        int len = nums.length;
        if (len <= 1) {
            return;
        }
        int idx = len - 2;
        while (idx >= 0 && nums[idx] >= nums[idx + 1]) {
            idx--;
        }
        if (idx == -1) {
            reverseArrFromLToR(nums, 0, len - 1);
            return;
        }
        //idx位置开始比之前小了，找到右边第一个比他大的数
        int l = idx + 1, r = len - 1;
        int v = nums[idx];
        while (l < r) {
            int mid = l + (r - l + 1 >> 1);
            if (nums[mid] > v) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        int tmp = nums[idx];
        nums[idx] = nums[l];
        nums[l] = tmp;
        reverseArrFromLToR(nums, idx + 1, len - 1);
        return;

    }


    private void reverseArrFromLToR(int[] arr, int l, int r) {
        while (l < r) {
            int tmp = arr[l];
            arr[l] = arr[r];
            arr[r] = tmp;
            l++;
            r--;
        }
    }
}
